import collections
from typing import List


# 求n以下的质数
def get_primes(n: int) -> list:
    if n < 2:
        return []

    num_list = [True] * n
    num_list[0], num_list[1] = False, False

    for i in range(2, int(pow(n, 0.5)) + 1):
        if num_list[i]:  # 如果i为质数(不是任何质数的倍数)
            num_list[i * i::i] = [False] * ((n - i * i - 1) // i + 1)  # 因为要包含i*i所以需要+1；因为n不在列表里，所以需要-1

    return [i for i in range(n) if num_list[i]]


# 分解质因子（小于等于10000）
primes = get_primes(101)


def get_prime_factors(x):
    res = set()
    for prime in primes:
        if prime > x:
            break
        while x % prime == 0:
            res.add(prime)
            x //= prime

    if x > 1:
        res.add(x)

    return res


class Solution:

    def __init__(self):
        self.primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]  # 50以下的质数列表

        self.nums = []
        self.graph = collections.defaultdict(set)
        self.ans = []

        self.cache = {}

    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:
        self.nums = nums
        for edge in edges:
            self.graph[edge[0]].add(edge[1])
            self.graph[edge[1]].add(edge[0])

        self.ans = [0] * len(nums)

        self.dfs(-1, 0, [-1] * 51)
        return self.ans

    def dfs(self, last, now, stat1):
        # print(now, ":", last, now, self.graph[now], "->", stat1)

        self.ans[now] = stat1[self.nums[now]]

        # 计算当前结点包含的因子列表
        factors = get_prime_factors(self.nums[now])

        # 计算当前因子列表覆盖的值
        contain_factors = [False] * 51

        for factor in factors:
            now_factor = factor
            while now_factor <= 50:
                contain_factors[now_factor] = True
                now_factor += factor

        stat2 = [now if not contain_factors[i] else stat1[i] for i in range(51)]

        for nxt in self.graph[now]:
            if nxt != last:
                self.dfs(now, nxt, stat2)


if __name__ == "__main__":
    # [-1,0,0,1]
    print(Solution().getCoprimes(nums=[2, 3, 3, 2], edges=[[0, 1], [1, 2], [1, 3]]))

    # [-1,0,-1,0,0,0,-1]
    print(Solution().getCoprimes(nums=[5, 6, 10, 2, 3, 6, 15], edges=[[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]]))
